// 力扣149. 直线上最多的点数
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }

        int maxCount = 0;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeCount = new HashMap<>();
            int duplicate = 0;
            int currentMax = 0;
            int x1 = points[i][0], y1 = points[i][1];

            for (int j = i + 1; j < n; j++) {
                int x2 = points[j][0], y2 = points[j][1];

                if (x1 == x2 && y1 == y2) {
                    duplicate++;
                    continue;
                }

                int dx = x2 - x1;
                int dy = y2 - y1;

                int g = gcd(dx, dy);
                if (g != 0) {
                    dx /= g;
                    dy /= g;
                }

                String slope = dx + "," + dy;
                slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
                currentMax = Math.max(currentMax, slopeCount.get(slope));
            }

            maxCount = Math.max(maxCount, currentMax + duplicate + 1);
        }

        return maxCount;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}